public class FindPivotIndex {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; // f[i]: 表示[0, i-1] 区间所有元素的和
        f[0] = 0; // 0 位置左侧数之和视为 `0`

        int[] g = new int[n]; // g[i]: 表示[i+1, n-1] 区间所有元素的和
        g[n-1] = 0; // n-1 位置右侧数之和视为 `0`

        for(int i = 1; i < n; i++) {
            f[i] = f[i-1] + nums[i-1];
        }
        for(int i = n- 2; i >= 0; i--) {
            g[i] = g[i+1] + nums[i+1];
        }

        for(int i = 0; i < n; i++) {
            if(f[i] == g[i]) {
                return i;
            }
        }
        return -1;
    }
}
